package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;

public class Problem081C {

	/**
	 * 动态规划的基本应用
	 * @param args
	 */
	public static void main(String[] args) throws IOException {

		Integer[][] ds = readData();
		Integer[][] ls = new Integer[80][];
		for (int i = 0; i < 80; i ++) {
			ls[i] = new Integer[80];
			for (int j = 0; j < 80; j ++) {
				ls[i][j] = 0;
			}
		}
		
		for (int k = 0; k < 79*2+1; k ++) {
			int mini = (k<=79)?0:k-79;
			int maxi = (k<=79)?k:79;
			for (int i = mini; i <= maxi; i ++) {
				int j = k-i;
				if (i == 0 && j == 0) {
					ls[i][j] = ds[i][j];
				} else if (i == 0 && j > 0) {
					ls[i][j] = ls[i][j-1] + ds[i][j];
				} else if (i > 0 && j == 0) {
					ls[i][j] = ls[i-1][j] + ds[i][j];
				} else {
					ls[i][j] = Math.min(ls[i][j-1], ls[i-1][j]) + ds[i][j];
				}
			}
		}
		System.out.println(ls[79][79]);
	}

	public static Integer[][] readData() throws IOException {

		URL url = Problem081C.class.getResource("Problem081.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));

		Integer[][] datas = new Integer[80][];
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = null;
		int r = 0;
		while ((line = br.readLine()) != null) {
			String[] tmp = line.split(",");
			datas[r] = new Integer[80];
			for (int c = 0; c < datas[r].length; c ++) {
				datas[r][c] = Integer.valueOf(tmp[c]);
			}
			r ++;
		}
		br.close();
		return datas;
	}
}
